22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例：

输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses

思路及算法

方法一：

昨天学习了『回溯算法』，这几天就练习这个

先祭出 回溯算法框架

result = []
def backtrack(路径, 选择列表):
    if 条件满足:
        result.add(路径)
        返回

    for 选择 in 选择列表:
        选择
        进入下一次层
        撤销选择

分析题目：

1. 有n对括号，即左右括号出现次数均为n
2. 一个有效的括号必定是左括号在前，右括号在后
3. 此题回溯算法的选择项只有两个 ( 和 )

我们可以定义两个变量专门记录左右括号已经出现的次数left 和 right

通过上面分析得到的信息，可以写出如下代码

result = []
def dfs(track, left, right):
	# 左括号数大于n, 右括号数大于n， 左括号数小于右括号数均是不满足 有效括号组合
	if left > n or right > n or left < right:
		return 
	
    # 左右都等于n，即满足
	if left == n and right == n:
    	result.append("".join(track))
    	return 
    
    for p in ['(', ')']:
        # 选择
    	track.append(p)
        if p == '(':
			dfs(track, left+1, right)
		else:
			dfs(track, left, right+1)
		# 回溯
        track.pop()

我在做这道题的时候，总想着怎么才能满足有效括号，看了题解突然觉得，有些题并不一定要直接找到正确解，而是将所有不合理的排除之后，剩下的就是答案

When you have eliminated the impossibles,whatever remains,however improbable,must be the truth.
排除一切不可能的，剩下的即使再不可能，那也是真相

——柯南 道尔《福尔摩斯探案集》

方法二：

方法一和方法二基本上是一样的，只是实现方法不同

方法一中的左右括号数往上加的，直到满足 left == n and right == n，在方法二中改为减，直到 left == 0 and right == 0

def dfs(track, left, right):

    if left == 0 and right == 0:
        result.append(track)
        return

    if left > 0:
        dfs(track + '(', left - 1, right)
        if right > left:
            dfs(track + ')', left, right-1)

感觉上来说，方法二比方法一代码更少，思维更灵活。方法一更传统，用模板以不变应万变

完整代码

代码一：

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        
        result = []
        
        def dfs(track, left, right):
            # 左括号数大于n, 右括号数大于n， 左括号数小于右括号数均是不满足 有效括号组合
            if left > n or right > n or left < right:
                return 
            # 左右都等于n，即满足
            if left == n and right == n:
                result.append("".join(track))
                return 

            for p in ['(', ')']:
                # 选择
                track.append(p)
                if p == '(':
                    dfs(track, left+1, right)
                else:
                    dfs(track, left, right+1)
                # 回溯
                track.pop()
		
        dfs([], 0, 0)

        return result

代码二：

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        result = []
        def dfs(track, left, right):

            if left == 0 and right == 0:
                result.append(track)
                return

            if left > 0:
                dfs(track + '(', left - 1, right)
            if right > left:
                dfs(track + ')', left, right-1)
		
        dfs('', n, n)
        
        return result